A computer system may have a number of nodes communicating with each other through a bus. The nodes may be individual computers, controllers for mass storage devices, or other computer apparatus. A problem arising in such a system architecture is the problem of determining which node transmits next on the bus. For example, a first node may be presently transmitting a message on the bus. Upon the conclusion of that transmission, there may be several nodes seeking to begin transmission. If more than one node begins transmission at the same time, say at the completion of the transmission of the first node, then a data collision will occur. The problem of determining which node transmits next on a shared, multiple access, bus is termed the "arbitration problem".
A solution to the arbitration problem must satisfy at least three requirements: the first requirement is that the arbitration must substantially prevent data collisions; the second requirement is that the arbitration must be "fair", meaning that each node must have an equal opportunity to gain access to the bus for transmission of messages originating in that node; and the third requirement is that the arbitration solution must be "efficient", meaning that the time spent in arbitration should be minimized, as the time spent in arbitration detracts from the available bandwidth of the bus.
A solution to the arbitration problem for a shared bus is set forth in U.S. Pat. No. 4,560,985, entitled "Dual-Count, Round-Robin Distributed Arbitration Technique for Serial Buses" issued to Strecker, Buzynski, and Thompson, on Dec. 24, 1985, referred to hereinafter as the "Strecker et al." patent.
The solution to the arbitration problem disclosed by the Strecker et al. patent, substantially prevents collision of data transfers onto a shared bus, and is fair. The solution disclosed in the Strecker et al. patent requires that each node monitor the bus for a carrier signal in order to determine if the bus is free. And the absence of a carrier signal indicates that no other node is transmitting a message on the bus, and the bus is therefore free. Upon detecting that the bus is free, that is that no carrier signal is detected on the bus, each node begins counting a sequence of predetermined time intervals. The predetermined time interval is referred to as a "quiet slot". The time length of a quiet slot is determined by the speed of the interface electronics and the maximum time of travel of a signal on the bus. Upon detection of no carrier on the bus, a node desiring access to the bus waits a predetermined number of quiet slots. If the predetermined number of quiet slots elapses without another node's carrier being detected, then the node desiring access begins to transmit. For each node, two values of the number of predetermined quiet slots are provided, one high slot countdown number (and, hence, low priority) and one low slot countdown number (and, hence, high priority). Each node is assigned a unique "node number".
The low countdown number is N+1 quiet slots, where N is the node number. The high slot countdown number is N+M+1 quiet slots, where M is the maximum number of nodes attached to the bus.
Initially, when an exemplary node begins arbitration, it counts N+M+1 number of quiet slots, the high count number of quiet slots. If the countdown is interrupted by another node winning the arbitration, that is by the exemplary node detecting a carrier, then the exemplary node determines the node number of the winning node. When the winning node has a higher node number than the exemplary node, the exemplary node retains an N+M+1 countdown. If the winning node has a lower node number, the exemplary node changes to an N+1 countdown when the bus once again becomes free. As a result of the arbitration, when several nodes are competing for the bus, the node having the lowest countdown number wins the bus.
As each node wins the bus, the M number is added to its countdown value. Thus in order to win the bus again for a subsequent message transmission, it must count down N+M+1 quiet slots.
Thus, each competing node has a turn at the bus, starting with the lowest numbered node and going to the highest.
The arbitration apparatus disclosed by the Strecker et al. patent both substantially prevents data collisions from transmissions of different nodes desiring access to the bus, and provides substantially fair access to the bus for all nodes.
However, the apparatus taught by the Strecker et al. patent is inefficient in the use of bandwidth. Several situations arise in which inefficient use of bandwidth is particularly noticeable. One such situation is in the transmission of many short messages by a plurality of nodes. The time spent by the bus carrying messages is small compared with the time spent counting quiet slots. Another situation resulting in inefficient use of bandwidth is where a particular node desires to transmit a very long message and the length of the message exceeds the maximum length allowed by the bus protocol, and no other node desires to transmit on the bus. The node desiring to transmit the long message must, according to the bus protocol, break that message into a series of shorter message transmissions. In this situation, the node must count N+M+1 number of quiet slots between the end of one transmission and the beginning of the next transmission. And requiring the node to count this number of quiet slots leaves the bus idle for an excessive length of time, thereby unnecessarily reducing the available bandwidth of the bus.